package com.mj.listen2._08_动态规划;

/**
 * 最长公共子序列（Longest Common Subsequence，LCS）
 * [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3
 */
public class LCS {
    public static void main(String[] args) {
        System.out.println(lcs(new int[]{1, 3, 5, 9, 10}, new int[]{1, 4, 9, 10}));
    }

    /**
     * 一维数组
     */



    private static int lcs(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        // 定义一个二维数组，只有两行
        int[][] dp = new int[2][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            int row = i % 2;// i % 2 == i & 2;
            int preRow = (i - 1) % 2;
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[row][j] = dp[preRow][j - 1] + 1;
                } else {
                    dp[row][j] = Math.max(dp[preRow][j], dp[row][j - 1]);
                }
            }
        }
        return dp[nums1.length % 2][nums2.length];
    }

    private static int lcs2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        // 定义一个二维数组
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }

    /**
     * 递归实现
     */
    static int lcs1(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return 0; // 检测非法数据
        if (nums2 == null || nums2.length == 0) return 0; // 检测非法数据
        return lcs1(nums1, nums1.length, nums2, nums2.length);
    }

    /**
     * 求nums1前i个元素和nums2前j个元素的最长g公共子序列长度
     *
     * @param nums1
     * @param i
     * @param nums2
     * @param j
     */
    static int lcs1(int[] nums1, int i, int[] nums2, int j) {
        if (i == 0 || j == 0) return 0;
        // 最后一个元素相等, 返回前面的公共子序列长度 + 1
        if (nums1[i - 1] == nums2[j - 1]) {
            // lcs(nums1, i - 1, nums2, j - 1) 表示前面公共子序列长度
            return lcs1(nums1, i - 1, nums2, j - 1) + 1;
        }

        // 最后一个元素不相等。返回[num1前i个元素，与num2前j-1个元素最长公共子序列长度] 和 [num1前i-1个元素，与num2前j个元素最长公共子序列长度]两者的最大值
        // dp(i,j)=max{dp(i,j-1),dp(i-1,j)}。dp(i,j)表示【num1前i个元素】与【num2前j个元素】的最长公共子序列长度
        return Math.max(
                lcs1(nums1, i, nums2, j - 1),
                lcs1(nums1, i - 1, nums2, j)
        );
    }
}
